Motion estimation is a predominant task of most modern video encoders. In the H.264 video encoding standard (T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 13, no. 7, pp. 560-576, 2003), when motion estimation is used to encode a frame, it is performed on every non-overlapping 16×16 block called current macroblock (in general, a block of 16×16 pixels is called a macroblock). Motion estimation is also performed inside each current macroblock, for block partitions of sizes 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, 4×4. These block partitions, or blocks, are called current blocks. Motion estimation consists of finding an optimal matching block matching candidate in a search area of size (2W+1)×(2W+1), where W is the full pel (picture element) length of the search area. The blocks inside this search area are called candidate blocks, and the search area can span over multiple reference frames, and quarter pel precision is used.
An exhaustive search algorithm (ESA) will obtain an optimal match by evaluating a cost function for each candidate block inside the search area. The best match, or optimal match, is the candidate with the lowest cost function value. The high computational complexity incurred by evaluating the cost function for all possible candidate blocks allowed in H.264 limits practical applications of ESA in modern encoders. Many algorithms reduce this computational complexity, and can be classified by whether or not they preserve optimality. Algorithms that do not preserve optimality often rely on the assumption of a monotonically increasing match criterion around the location of the optimal candidate block. When this assumption does not hold, accuracy of the motion estimation is reduced, as it will converge to a local minimum. Modern algorithms in this class include zonal search algorithms (A. M. Tourapis, O. C. Au, and M. L. Liou, “Predictive motion vector field adaptive search technique (PMVFAST): enhancing block-based motion estimation,” Proc. SPIE Visual Communications and Image Processing, vol. 4310, pp. 883-892, 2001; and A. M. Tourapis, “Enhanced predictive zonal search for single and multiple frame motion estimation,” Proc. SPIE Visual Communications and Image Processing, vol. 4671, pp. 1069-1079, 2002), which first evaluate a set of predictors in order to constrain a local diamond or square search to a very narrow zone of the search area.
Optimality preserving algorithms often rely on known inequalities, to avoid computing the cost function of candidate blocks during the search process. Recent algorithms in this class append more efficient filtering criteria to the successive elimination algorithm (SEA) (W. Li and E. Salari, “Successive elimination algorithm for motion estimation.,” IEEE Transactions on Image Processing, vol. 4, no. 1, pp. 105-7, January 1995, hereinafter Li). Others (X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A multilevel successive elimination algorithm for block matching motion estimation.,” IEEE Transactions on Image Processing, vol. 9, no. 3, pp. 501-504, March 2000, hereinafter Gao; and C. Zhu, W.-S. Qi, and W. Ser, “Predictive fine granularity successive elimination for fast optimal block-matching motion estimation.,” IEEE Transactions on Image Processing, vol. 14, no. 2, pp. 213-221, February 2005, hereinafter Zhu), in their own way propose the use of partitions inside blocks to improve filtering efficiency.
Others (M. Z. Coban and R. M. Mersereau, “A fast exhaustive search algorithm for rate-constrained motion estimation.,” IEEE Transactions on Image Processing, vol. 7, no. 5, pp. 769-773, May 1998, hereinafter Coban) modified the SEA to take into account the number of bits required to encode the motion vector of a candidate block, by altering the SEA criterion into a rate-constrained filtering criterion. This alteration is in line with the H.264 standard recommendations (K. P. Lim, G. J. Sullivan, and T. Wiegand, “Text description of joint model reference encoding methods and decoding concealment methods,” JVT-R095, JVT of ISO/IEC MPEG and ITU-T, January 2006, hereinafter Lim) that the optimal matching candidate block should be the best rate-constrained match. H.264-based SEA algorithms have been proposed (M. Yang, H. Cui, and K. Tang, “Efficient tree structured motion estimation using successive elimination,” IEE Proceedings Vision, Image and Signal Processing, vol. 151, no. 5, pp. 369-377, October 2004, hereinafter Yang; and T. Toivonen and J. Heikkila, “Fast full search block motion estimation for H.264/AVC with multilevel successive elimination algorithm,” in ICIP '04. International Conference on Image Processing, October 2004, vol. 3, pp. 1485-1488, hereinafter Toivonen).
Another way the filtering criterion can be improved is via the candidate block search ordering used for motion estimation. Spiral search ordering is known to outperform a raster search ordering, and tends to evaluate better candidate blocks earlier in the search process, which in turn improves the filtering criterion and allows more candidate blocks to be skipped. That is why the spiral search ordering is used in many implementations of SEA-based algorithms (Zhu, Coban, and Yang). This must however not to be confused with SpiralPDE (J. N. Kim and T. S. Choi, “A fast full-search motion-estimation algorithm using representative pixels and adaptive matching scan,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 7, pp. 1040-1048, October 2000), which is a spiral pattern used to sum the elements of a block.
However, conventional search algorithms such as raster and spiral search algorithms discussed hereinabove, can impair the filtering criterion of rate-constrained successive elimination algorithms. It would be advantageous to provide a method and system for overcoming this problem.